{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Two Sum Less Than K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: twoSumLessThanK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #小于 K 的两数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和整数 <code>k</code> ，返回最大和 <code>sum</code> ，满足存在 <code>i < j</code> 使得 <code>nums[i] + nums[j] = sum</code> 且 <code>sum < k</code> 。如果没有满足此等式的 <code>i,j</code> 存在，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [34,23,1,24,75,33,54,8], k = 60\n",
    "<strong>输出：</strong>58\n",
    "<strong>解释：</strong>\n",
    "34 和 24 相加得到 58，58 小于 60，满足题意。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [10,20,30], k = 15\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>\n",
    "我们无法找到和小于 15 的两个元素。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 100</code></li>\n",
    "\t<li><code>1 <= nums[i] <= 1000</code></li>\n",
    "\t<li><code>1 <= k <= 2000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [two-sum-less-than-k](https://leetcode.cn/problems/two-sum-less-than-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [two-sum-less-than-k](https://leetcode.cn/problems/two-sum-less-than-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[34,23,1,24,75,33,54,8]\\n60', '[10,20,30]\\n15']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, A: List[int], K: int) -> int:\n",
    "        if min(A) > K: return -1\n",
    "        left, right = 0, len(A) - 1\n",
    "        max_val = -1\n",
    "        A = sorted(A)\n",
    "        while left < right:\n",
    "            sum_val = A[left] + A[right]\n",
    "            if sum_val >= K:\n",
    "                right -= 1\n",
    "            else:\n",
    "                max_val = max(max_val, sum_val)\n",
    "                left += 1\n",
    "        return max_val\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        length=len(nums)\n",
    "        max = 0\n",
    "        if length ==1:\n",
    "            return -1\n",
    "        elif nums[0] + nums[1] >=k:\n",
    "            return -1\n",
    "        else:\n",
    "            for i in range(length-1):\n",
    "                for j in range(i+1,length): # 必须循环完毕才能确定最大的sum\n",
    "                    if nums[i] + nums[j]<k and nums[i]+nums[j]>max:\n",
    "                        max = nums[i] + nums[j]\n",
    "        return max\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        for i in range(len(nums)-1):\n",
    "            # if nums[i]<k//2:\n",
    "            left,right = i+1,len(nums)\n",
    "            while(left<right):\n",
    "                mid = left + (right-left)//2\n",
    "                sumup = nums[mid]+nums[i]\n",
    "                if sumup<k:\n",
    "                    res = max(res,sumup)\n",
    "                    left = mid+1\n",
    "                else:\n",
    "                    right = mid\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return -1\n",
    "        \n",
    "        nums.sort()\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if nums[i] >= k:\n",
    "                break\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] + nums[j] >= k:\n",
    "                    break\n",
    "                ans = max(ans, nums[i] + nums[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            m = nums[left] + nums[right]\n",
    "            if m >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                res = max(res, m)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            m = nums[left] + nums[right]\n",
    "            if m >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "            if m < k:\n",
    "                res = max(res, m)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            curr = nums[left] + nums[right]\n",
    "            if curr >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                result = max(result, curr)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        # 两种极端情况\n",
    "        if nums[-2] + nums[-1] < k: #最大和小于 k\n",
    "            return nums[-2] + nums[-1]\n",
    "        if nums[0] + nums[1] >= k: #最小和大于等于 k\n",
    "            return -1\n",
    "\n",
    "        res = -1\n",
    "        \n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            cur_sum = nums[i] + nums[j]\n",
    "            if cur_sum >= k:\n",
    "                j -= 1\n",
    "            elif cur_sum < k:\n",
    "                res = max(res, cur_sum)\n",
    "                # res = cur_sum\n",
    "                i += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            m = nums[left] + nums[right]\n",
    "            if m >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "            if m < k:\n",
    "                res = max(res, m)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "               \n",
    "        nums.sort()\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            m = nums[left] + nums[right]\n",
    "            if m >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "            if m < k:\n",
    "                res = max(res, m)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return -1\n",
    "        \n",
    "        nums.sort()\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if nums[i] >= k:\n",
    "                break\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] + nums[j] >= k:\n",
    "                    break\n",
    "                ans = max(ans, nums[i] + nums[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        # 两种极端情况\n",
    "        if nums[-2] + nums[-1] < k: #最大和小于 k\n",
    "            return nums[-2] + nums[-1]\n",
    "        if nums[0] + nums[1] >= k: #最小和大于等于 k\n",
    "            return -1\n",
    "\n",
    "        res = -1\n",
    "        \n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            cur_sum = nums[i] + nums[j]\n",
    "            if cur_sum >= k:\n",
    "                j -= 1\n",
    "            elif cur_sum < k:\n",
    "                res = max(res, cur_sum)\n",
    "                i += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        x = -1\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                cur = nums[i]+nums[j]\n",
    "                if cur < k and cur > x:\n",
    "                    x = cur\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < k:\n",
    "                res = max(res, nums[left] + nums[right])\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "           return -1\n",
    "           \n",
    "        nums.sort()\n",
    "        if nums[0] + nums[1] > k:\n",
    "            return -1\n",
    "            \n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "           return -1\n",
    "           \n",
    "        nums.sort()\n",
    "        if nums[0] + nums[1] > k:\n",
    "            return -1\n",
    "            \n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans_num = -1\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i] + nums[j] < k:\n",
    "                    ans_num = max(ans_num,nums[i] + nums[j])\n",
    "                else:\n",
    "                    break\n",
    "        return ans_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "               \n",
    "        nums.sort()\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            curr = nums[left] + nums[right]\n",
    "            if curr >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                result = max(result, curr)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        \n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] > k:\n",
    "                continue\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                 if nums[i] + nums[j] < k:\n",
    "                     max1 = max(max1, nums[i] + nums[j])\n",
    "                         \n",
    "        return -1 if not max1 else max1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        # sort\n",
    "        nums.sort()\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 1 or nums[0] + nums[1] >= k:\n",
    "            return -1\n",
    "        \n",
    "        left, right, maxSum = 0, n - 1, 0\n",
    "        while left < right:\n",
    "            sum = nums[left] + nums[right]\n",
    "            if sum >= k:\n",
    "                right -= 1\n",
    "            elif sum < k:\n",
    "                maxSum = max(maxSum, sum)\n",
    "                left += 1\n",
    "        return maxSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        sump=-1\n",
    "        i,j=0,len(nums)-1\n",
    "        while i<j:\n",
    "            aa=nums[i]+nums[j]\n",
    "            if aa>=k:\n",
    "                j-=1\n",
    "            else:\n",
    "                sump=max(sump,aa)\n",
    "                i+=1\n",
    "        return sump\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        length=len(nums)\n",
    "        max = 0\n",
    "        if length ==1:\n",
    "            return -1\n",
    "        elif nums[0] + nums[1] >=k:\n",
    "            return -1\n",
    "        else:\n",
    "            for i in range(length-1):\n",
    "                for j in range(i+1,length):\n",
    "                    if nums[i] + nums[j]<k and nums[i]+nums[j]>max:\n",
    "                        max = nums[i] + nums[j]\n",
    "        return max\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans_nums = -1\n",
    "        nums.sort()\n",
    "        # for i in range(len(nums)-1):\n",
    "        #     for j in range(i+1,len(nums)):\n",
    "        #         if nums[i] + nums[j] < k:\n",
    "        #             ans_num = max(ans_num,nums[i] + nums[j])\n",
    "        #         else:\n",
    "        #             break\n",
    "        # return ans_num\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < k:\n",
    "                ans_nums = max(ans_nums,nums[left]+nums[right])\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return ans_nums\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "           return -1\n",
    "        nums.sort()\n",
    "        if nums[0] + nums[1] > k:\n",
    "            return -1\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "               \n",
    "        nums.sort()\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        \n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] > k:\n",
    "                continue\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                 if nums[i] + nums[j] < k:\n",
    "                     max1 = max(max1, nums[i] + nums[j])\n",
    "                         \n",
    "        return -1 if not max1 else max1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if not nums or  len(nums)< 2:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = -1\n",
    "        if nums[0] >= k/2:\n",
    "            return -1\n",
    "\n",
    "        l,r = 0, n-1\n",
    "\n",
    "        while l<r:\n",
    "            if nums[l] + nums[r] < k:\n",
    "                res = max(res, nums[l] + nums[r])\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return res\n",
    "\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            m = nums[left] + nums[right]\n",
    "            if m >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "            if m < k:\n",
    "                res = max(res, m)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        answer = -1\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            j = bisect_left(nums, k - nums[i], i + 1) - 1\n",
    "            if j > i:\n",
    "                answer = max(answer, nums[i] + nums[j])\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        res = -1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                res = max(res, nums[left] + nums[right])\n",
    "                left += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "               \n",
    "        nums.sort()\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "           return -1\n",
    "           \n",
    "        nums.sort()\n",
    "        if nums[0] + nums[1] > k:\n",
    "            return -1\n",
    "            \n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.append(k+1)\n",
    "        nums.sort()\n",
    "        nums = nums[:nums.index(k+1)]\n",
    "\n",
    "        m = -float('inf')\n",
    "        left,right = 0,len(nums)-1\n",
    "        while left <  right:\n",
    "            # middle = left + (right -left)//2\n",
    "            if nums[left]+nums[right] < k:\n",
    "                m = max(m,nums[left]+nums[right])\n",
    "                left = left +1\n",
    "            else:\n",
    "                right = right - 1\n",
    "        \n",
    "        if m != -float('inf'):\n",
    "            return m\n",
    "        else:\n",
    "            return -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        max_sum = float('-inf')\n",
    "        right = length - 1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                max_sum = max(max_sum, nums[left] + nums[right])\n",
    "                left += 1\n",
    "        return max_sum if max_sum != float('-inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        answer = -1\n",
    "        left, right = 0, len(nums) - 1\n",
    "\n",
    "        while left < right:\n",
    "            sum = nums[left] + nums[right]\n",
    "\n",
    "            if sum < k:\n",
    "                answer = max(answer, sum)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        l, r, res = 0, len(nums) - 1, -1\n",
    "        nums.sort()\n",
    "        while l < r:\n",
    "            two = nums[l] + nums[r]\n",
    "            if two >= k:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res = max(res, two)\n",
    "                l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()  # 对数组进行排序\n",
    "        left, right = 0, len(nums) - 1\n",
    "        max_sum = -1\n",
    "\n",
    "        while left < right:\n",
    "            current_sum = nums[left] + nums[right]\n",
    "\n",
    "            if current_sum < k:\n",
    "                max_sum = max(max_sum, current_sum)\n",
    "                left += 1  # 增加左指针以增加当前的 sum\n",
    "            else:\n",
    "                right -= 1  # 减小右指针以减小当前的 sum\n",
    "\n",
    "        return max_sum\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "               \n",
    "        nums.sort()\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        res = -1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < k:\n",
    "                res = max(res, nums[left] + nums[right])\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        max1, start, end = -2, 0, len(nums) - 1\n",
    "        nums.sort()\n",
    "        while start < end:\n",
    "            if nums[start] + nums[end] < k:\n",
    "                max1 = max(max1, nums[start] + nums[end])\n",
    "                start += 1\n",
    "            else:\n",
    "                end-= 1\n",
    "        return max(max1, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "       \n",
    "        \n",
    "        max1 = 0\n",
    "        \n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] > k:\n",
    "                continue\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                 if nums[i] + nums[j] < k:\n",
    "                     max1 = max(max1, nums[i] + nums[j])\n",
    "                         \n",
    "        return -1 if not max1 else max1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "           return -1\n",
    "           \n",
    "        nums.sort()\n",
    "        if nums[0] + nums[1] > k:\n",
    "            return -1\n",
    "            \n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left,right = 0,len(nums)-1\n",
    "        maxsum = -1\n",
    "        while(left<right):\n",
    "            if  nums[left]+nums[right]<k:\n",
    "                maxsum = max(nums[left]+nums[right],maxsum)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return maxsum\n",
    "              \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        r = -1\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                t = nums[i]+nums[j]\n",
    "                if t < k:\n",
    "                    r = max(r, t)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "           return -1\n",
    "           \n",
    "        nums.sort()\n",
    "        if nums[0] + nums[1] > k:\n",
    "            return -1\n",
    "            \n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = -1\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                sum = nums[i]+nums[j]\n",
    "                if sum < k:\n",
    "                    res = max(sum, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right, maxval = 0, len(nums)-1, -1\n",
    "        while left < right:\n",
    "            curval = nums[left] + nums[right]\n",
    "            if curval < k:\n",
    "                maxval = max(maxval, curval)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return maxval\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = -1\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                sm = nums[i] + nums[j]\n",
    "                if sm < k:\n",
    "                    res = max(res, sm)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            curr = nums[left] + nums[right]\n",
    "            if curr >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                result = max(result, curr)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        left, right = 0, n-1\n",
    "        ans = -1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < k:\n",
    "                if k - ans > k - (nums[left] + nums[right]):\n",
    "                    ans = nums[left] + nums[right]\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        L, R = 0, n-1\n",
    "        while L < R:\n",
    "            if nums[L] + nums[R] >= k:\n",
    "                R -= 1\n",
    "            else:\n",
    "                res = max(res, nums[L] + nums[R])\n",
    "                L += 1\n",
    "        return res\n",
    "\n",
    "# 作者：HanXin\n",
    "# 链接：https://leetcode.cn/problems/two-sum-less-than-k/solutions/625402/c-python3-pai-xu-shuang-zhi-zhen-ijzhe-g-oo73/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = -1\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i]+nums[j]<k:\n",
    "                    res = max(res, nums[i]+nums[j])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        max1, start, end = -2, 0, len(nums) - 1\n",
    "        nums.sort()\n",
    "        while start < end:\n",
    "            if nums[start] + nums[end] < k:\n",
    "                max1 = max(max1, nums[start] + nums[end])\n",
    "                start += 1\n",
    "            else:\n",
    "                end-= 1\n",
    "        return max(max1, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "       \n",
    "        \n",
    "        max1 = 0\n",
    "        \n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] > k:\n",
    "                continue\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                 if nums[i] + nums[j] < k:\n",
    "                     max1 = max(max1, nums[i] + nums[j])\n",
    "                         \n",
    "        return -1 if not max1 else max1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = -1\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            j = bisect.bisect_left(nums, k-nums[i])-1\n",
    "            if j > i:\n",
    "                res = max(res, nums[i]+nums[j])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        # record index \n",
    "        # sort \n",
    "        # return maxsum\n",
    "        nums.sort()\n",
    "        res = -float('inf')\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left<right:\n",
    "            temp = nums[left]+nums[right]\n",
    "            if temp < k:\n",
    "                res = max(res, temp)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "\n",
    "        return res if res != -float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < k:\n",
    "                res = max(nums[left] + nums[right], res)\n",
    "                left += 1\n",
    "                \n",
    "            elif nums[left] + nums[right] >= k:\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "       \n",
    "        \n",
    "        max1 = 0\n",
    "        \n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] > k:\n",
    "                continue\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                 if nums[i] + nums[j] < k:\n",
    "                     max1 = max(max1, nums[i] + nums[j])\n",
    "                         \n",
    "        return -1 if not max1 else max1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.append(k+1)\n",
    "        nums.sort()\n",
    "        nums = nums[:nums.index(k+1)]\n",
    "\n",
    "        m = -float('inf')\n",
    "        left,right = 0,len(nums)-1\n",
    "        while left <  right:\n",
    "            # middle = left + (right -left)//2\n",
    "            if nums[left]+nums[right] < k:\n",
    "                m = max(m,nums[left]+nums[right])\n",
    "                left = left +1\n",
    "            else:\n",
    "                right = right - 1\n",
    "        \n",
    "        if m != -float('inf'):\n",
    "            return m\n",
    "        else:\n",
    "            return -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "           return -1\n",
    "        nums.sort()\n",
    "        if nums[0] + nums[1] > k:\n",
    "            return -1\n",
    "        nums.reverse()\n",
    "        \n",
    "        max1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < k:\n",
    "                for j in range(i + 1, len(nums)):\n",
    "                    if nums[i] + nums[j] < k:\n",
    "                        max1 = max(max1, nums[i] + nums[j])\n",
    "                        break\n",
    "        return max1 if max1 else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        r=n-1\n",
    "        nums.sort()\n",
    "        l=0\n",
    "        ans=-1\n",
    "        while l<r :\n",
    "            if nums[l]+nums[r]>=k:\n",
    "                r=r-1\n",
    "            else:\n",
    "                ans=max(ans,nums[l]+nums[r])\n",
    "                l=l+1\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right, res = 0, len(nums) - 1, -1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < k:\n",
    "                res = max(nums[left] + nums[right], res)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = -1\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            curr = nums[left] + nums[right]\n",
    "            if curr >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                result = max(result, curr)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        print(nums)\n",
    "        left,right=0,len(nums)-1\n",
    "        while left<right:\n",
    "            while nums[right]>k:\n",
    "                right -= 1\n",
    "            s=nums[left]+nums[right]\n",
    "            print('s',s,'left',left,'right',right)\n",
    "            if s >= k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                res = max(res,s)\n",
    "                left += 1\n",
    "        return res\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoSumLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans = -1\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        print(len(nums))\n",
    "        for i, num in enumerate(nums):\n",
    "            #if i == len(nums) - 1:\n",
    "            #    break\n",
    "            left = i + 1\n",
    "            right = len(nums)\n",
    "\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] < k - num:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            print(right)\n",
    "            if right - 1 >= i + 1:\n",
    "                ans = max(ans, num + nums[right - 1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
